package solution.design;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-09-23 10:49
 */

/*341. 扁平化嵌套列表迭代器*/
public class NestedIterator implements Iterator<Integer> {

   /* private Iterator<Integer> iterator;

    public solution.design.NestedIterator(List<solution.design.NestedInteger> nestedList) {
        List<Integer> res=new ArrayList<>();
        for (solution.design.NestedInteger ne:nestedList) {
            travarse(ne,res);
        }
        this.iterator=res.iterator();
    }
    // 遍历以 root 为根的多叉树，将叶子节点的值加入 result 列表
    private void travarse(solution.design.NestedInteger root,List<Integer> res){
        if (root.isInteger()){
            res.add(root.getInteger());
            return;
        }
        for (solution.design.NestedInteger node:root.getList()) {
            travarse(node,res);
        }
    }
    @Override
    public Integer next() {
        return iterator.next();
    }

    @Override
    public boolean hasNext() {
        return iterator.hasNext();
    }*/

//迭代器惰性求值的特性:调用hasNext时，如果nestedList的第一个元素是列表类型，则不断展开这个元素，直到第一个元素是整数类型。
    private LinkedList<NestedInteger> list;
    public NestedIterator(List<NestedInteger> nestedList) {
        // 不直接用 nestedList 的引用，是因为不能确定它的底层实现
        // 必须保证是 LinkedList，否则下面的 addFirst 会很低效
        list=new LinkedList<>(nestedList);
    }

    @Override
    public Integer next() {
        return list.remove(0).getInteger();
    }

    @Override
    public boolean hasNext() {
        // 循环拆分列表元素，直到列表第一个元素是整数类型
        while (!list.isEmpty()&&!list.get(0).isInteger()){
            List<NestedInteger> first=list.remove(0).getList();
            // 将第一个列表打平并按顺序添加到开头,需要挨个插入到开头，所有从后向前插入得到正确顺序
            for (int i = first.size()-1; i >=0 ; i--) {
                list.addFirst(first.get(i));
            }
        }
        return !list.isEmpty();
    }

}
